<?php

/**
 * 堆通常是一个可以被看做一棵完全二叉树的数组对象。
 * 堆满足下列性质：
 * 堆中某个节点的值总是不大于或不小于其父节点的值。
 * 堆总是一棵完全二叉树。
 * 某一个节点的下标为 $i ，则其左子节点的下标为 $i * 2 ，其右子节点的下标为 $i * 2 + 1
 */
class 堆
{
    public $堆数组 = [];
    public static $堆容量 = 10;
    public $堆长度 = 0;

    public function 插入(int $新元素)
    {
        if ($this->堆长度 >= self::$堆容量) {
            throw new Exception('堆满了');
        }

        ++$this->堆长度;
        // 放数组最后面
        $this->堆数组[$this->堆长度] = $新元素;

        $当前下标 = $this->堆长度;
        $父节点 = floor($当前下标 / 2);

        $this->自下往上堆化($当前下标, $父节点);

        return $this->堆数组;
    }

    public function 删除大顶堆堆顶元素()
    {
        if ($this->堆长度 <= 0) {
            throw new Exception('堆空了');
        }
        $堆顶元素 = $this->堆数组[1];
        $this->堆数组[1] = $this->堆数组[$this->堆长度];
        unset($this->堆数组[$this->堆长度]);
        --$this->堆长度;

        $this->自顶向下堆化(1);

        return $堆顶元素;
    }

    public function 数组建堆(&$输入数组)
    {
        $堆最大下标 = count($输入数组) - 1;
        for ($i = floor($堆最大下标 / 2); $i >= 1; --$i) { 
            $this->针对给定堆自顶向下堆化($输入数组, $堆最大下标, $i);
        }

        return $输入数组;
    }

    public function 堆排序($输入数组)
    {
        $this->数组建堆($输入数组);
        $堆最大下标 = count($输入数组) - 1;

        while ($堆最大下标 > 1) {
            $this->交换($输入数组, 1, $堆最大下标);
            --$堆最大下标;
            $this->针对给定堆自顶向下堆化($输入数组, $堆最大下标, 1);
        }

        return $输入数组;
    }

    public function 交换(&$堆数组, $下标1, $下标2)
    {
        $临时变量 = $堆数组[$下标1];
        $堆数组[$下标1] = $堆数组[$下标2];
        $堆数组[$下标2] = $临时变量;
    }

    public function 自下往上堆化($当前下标, $父节点)
    {
        while ($父节点 > 0 && $this->堆数组[$父节点] < $this->堆数组[$当前下标]) {
            $this->交换($this->堆数组, $当前下标, $父节点);
            $当前下标 = $父节点;
            $父节点 = floor($当前下标 / 2);
        }
    }

    public function 自顶向下堆化($当前下标)
    {
        while (true) {
            $较大值下标 = $当前下标;
            // 顶节点与左子节点进行比较
            if ($当前下标 * 2 <= $this->堆长度 && $this->堆数组[$当前下标] < $this->堆数组[$当前下标 * 2]) {
                $较大值下标 = $当前下标 * 2;
            }

            // 右子节点与上轮比较的大值进行比较
            if ($当前下标 * 2 + 1 <= $this->堆长度 && $this->堆数组[$较大值下标] < $this->堆数组[$当前下标 * 2 + 1]) {
                $较大值下标 = $当前下标 * 2 + 1;
            }

            // 当上两轮比较完之后，发现啥也没干啊，那就退出，说明不用在比较了
            if ($当前下标 == $较大值下标) {
                break;
            }

            $this->交换($this->堆数组, $当前下标, $较大值下标);
            $当前下标 = $较大值下标;
        }
    }

    public function 针对给定堆自顶向下堆化(&$给定数组, $堆长度, $当前下标)
    {
        while (true) {
            $较大值下标 = $当前下标;
            // 顶节点与左子节点进行比较
            if ($当前下标 * 2 <= $堆长度 && $给定数组[$当前下标] < $给定数组[$当前下标 * 2]) {
                $较大值下标 = $当前下标 * 2;
            }

            // 右子节点与上轮比较的大值进行比较
            if ($当前下标 * 2 + 1 <= $堆长度 && $给定数组[$较大值下标] < $给定数组[$当前下标 * 2 + 1]) {
                $较大值下标 = $当前下标 * 2 + 1;
            }

            // 当上两轮比较完之后，发现啥也没干啊，那就退出，说明不用在比较了
            if ($当前下标 == $较大值下标) {
                break;
            }

            $this->交换($给定数组, $当前下标, $较大值下标);
            $当前下标 = $较大值下标;
        }
    }
}

$实例 = new 堆();

$结果数组 = $实例->插入(5);
$结果数组 = $实例->插入(3);
$结果数组 = $实例->插入(6);
$结果数组 = $实例->插入(1);
$结果数组 = $实例->插入(7);
$结果数组 = $实例->插入(8);

print_r($结果数组);

$堆顶元素 = $实例->删除大顶堆堆顶元素();

print_r($堆顶元素);
echo PHP_EOL;
print_r($实例->堆数组);

$输入数组 = [0, 6, 1, 8, 5, 2, 0, 9, 7];
$结果数组 = $实例->数组建堆($输入数组);
print_r($结果数组);

$输入数组 = [0, 6, 1, 8, 5, 2, 0, 9, 7];
$排序结果 = $实例->堆排序($输入数组);
print_r($排序结果);